Distributed processing networks are gaining increasing importance in our information-based society. FIG. 1 depicts a network topology of a simple data network. The network 100 comprises a plurality of routers 104a–g, a transit network 108, and a stub network 112, all interconnected by links 116a–i. As will be appreciated, a router is a device connecting two or more networks that routes incoming data or packets to an appropriate network/node; a transit network is a network containing more than router; a stub network is a network that is not configured to transit packets through the network from one router to another; and a link is a communication channel between two or more nodes. Each of the routers is typically attached to a link via one or more interfaces, such as interfaces 120a–n. The simple network of FIG. 1 is divided into two protocol regions with the dashed line 124 being the boundary between the two regions. Router 104c is located on the boundary 124 and is referred to herein as an area border router while the other routers 104a–b and d–g are not area border routers. One or more protocol regions are often autonomous systems. An autonomous system is a collection of networks controlled by a single administrative authority.
In a packet-switched network, the technique used to route a packet through interconnected networks depends on the routing protocol. Most protocols fall into one of two categories, distance-vector algorithms (which determine the distance between source and destination nodes by calculating the number of router hops a packet traverses en route from the source network to the destination network) and link-state algorithms (which use link state advertisement or LSA (containing the names and various cost metrics of a router's neighbors) to keep routers informed about links in the network). Rather than storing actual paths (which is the case with distance-vector algorithms), link-state algorithms store the information needed to generate such paths. Examples of router protocols using distance-vector algorithms include RIP and RIP-2 and using link-state algorithms include Open Shortest Path First or OSPF, OSI's IS-IS, EIGRP, and Netware's Link Service's Protocol (NLSP).
Routers and other network components are typically managed using a network management system. Network management systems perform network maintenance, identify possible security problems in the network, locate equipment, module, subassembly, and card failures, locate circuit outages, monitor levels of performance (e.g., bit error rates or BERs, loss of synchronization, etc.) and permit rapid and accurate quantification of network usage and traffic levels. Examples of network management systems used for performing the foregoing tasks include Hewlett-Packard's OpenView™, IBM's Netview™, and Digital Equipment Corporation's Enterprise Management Architecture or EMA™.
For optimal operation of network management systems, an accurate, detailed map of the network or OSI layer 3 topologies is commonly required. Such a map not only facilitates operation of the network management system but also permits newly attached hosts to be properly located and configured for the network (to avoid adversely impacting network performance) and existing hosts to be properly located for the newly attached host. In common practice, a detailed map of the network's topology is, in whole or part, unavailable to network management personnel. This can be due to poor record keeping, the sheer size and complexity of some networks, and the lack of central management of a network, such as where a network includes a number of autonomous systems or enterprises.
Simple Network Management Protocol or SNMP algorithms for discovering automatically network layer topology are used in many network management tools. The SNMP algorithms can take several approaches. In one approach known as the “hop-by-hop” approach, the algorithm accesses standard routing SNMP-Management Information Base or MIB information in each router on a hop-by-hop basis. As used herein, a “hop” refers to a portion of a route that has no intermediate nodes and “MIB” is the set of managed objects or variables that can be managed as defined by SNMP. MIB objects or variables are typically defined by the set of rules known as Structure of Management Information or SMI. As will be appreciated, MIB information is stored in the memory of any SNMP router. In another approach, vendor-specific proprietary algorithms are used to generate the topology. An example of such a solution is CDP™ by Cisco Systems. Such proprietary algorithms typically rely on the vendor-specific extensions to the standard SNMP MIBs that are generally not useful in a multi-vendor network.
SNMP network topology discovery algorithms are typically unable to ascertain Layer 3 topology when the routers in a network support differing routing protocols and/or are uncontactable. A router can be uncontactable for a variety of reasons including the use of improper credentials, a down state of the contacted interface, an inaccessible or nonexistent SNMP agent in the router, etc. This problem is illustrated by FIG. 2. Referring to FIG. 2, router 200 supports Routing Information Protocol or RIP and is SNMP contactable, routers 204, 208, and 212 support the Open Shortest Path First or OSPF protocol and are SNMP contactable, router 216 supports OSPF but is not SNMP contactable, and finally router 220 supports OSPF and RIP and is SNMP contactable. If the topology discovery algorithm initially contacts router 200, it will, by the hop-by-hop approach, be able to discover routers 200, 220 and 216. When the algorithm contacts router 216, which is not SNMP contactable, the algorithm will be unable to discover routers 204, 208, and 212. This is so because the algorithm will be unable to access the MIB information in router 216, thereby preventing the algorithm from learning of the existence of these routers.